public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
//        if(A == null){
//            return true;
//        }
//        if(A.next == null){
//            return true;
//        }
//        ListNode newHead = new ListNode(0);
//        ListNode newTail = newHead;
//        for(ListNode cur = A; cur != null; cur = cur.next){
//            ListNode newNode = new ListNode(cur.val);
//            newTail.next = newNode;
//            newTail = newNode;
//        }
//        newHead = newHead.next;
//        ListNode prev = null;
//        ListNode cur = newHead;
//        ListNode next = cur.next;
//        while(cur != null){
//            next = cur.next;
//            if(next == null){
//                newHead = cur;
//            }
//            cur.next = prev;
//            prev = cur;
//            cur = cur.next;
//        }
//        while(newHead != null && A != null){
//            if(newHead.val != A.val){
//                return false;
//            }
//            newHead = newHead.next;
//            A = A.next;
//        }
//        if(newHead == null && A == null){
//            return true;
//        }
//        return false;
//    }
        public int size(ListNode A){
            int size = 0;
            for(ListNode cur = A; cur != null;cur = cur.next){
                size++;

            }
            return size;

        }
        public boolean chkPalindrome(ListNode A){
            // write code here
            if (A == null) {
                return true;
            }
            if (A.next == null) {
                return true;
            }
            int mid = size(A) / 2;
            ListNode B = A;
            for (int i = 0; i < mid; i++) {
                B = B.next;
            }
            ListNode prev = null;
            ListNode cur = B;
            //ListNode next = cur.next;
            while (cur != null) {
                ListNode next = cur.next;
                if (next == null) {
                    B = cur;
                }
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            while (A != null && B != null) {
                if (A.val != B.val) {
                    return false;
                }
                A = A.next;
                B = B.next;
            }
            return true;
        }


}

class ListNode{
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
